#include "ai_search_mt.h"



mt_search_algorithm::mt_search_algorithm()
{
	name = "Search algorithm MT";
	lock_levels_list = new QReadWriteLock();
	lock_searched_states_list = new QReadWriteLock();
	lock_counters = new QReadWriteLock();
	lock_thread_counter = new QReadWriteLock();
	lock_workers_list = new QReadWriteLock();
	searched_states_list = 0;
	search_tree = 0;
	state_levels = 0;
	workers = 0;
	nodes_to_search = 0;
	searched_nodes = 0;
	running_threads = 0;
};



mt_search_algorithm::~mt_search_algorithm()
{
	delete lock_levels_list;
	delete lock_searched_states_list;
	delete lock_counters;
	delete lock_thread_counter;
	delete lock_workers_list;
	if ( search_tree != 0 )
		delete search_tree;
	if ( workers != 0 )
	{
		if ( !workers->empty() )
		{
			for ( list< sa_worker* >::iterator it = workers->begin(); it != workers->end(); ++it )
				delete *it;
			workers->clear();
		}
		delete workers;
	}
	if ( state_levels != 0 )
		delete state_levels;
	if ( searched_states_list != 0 )
		delete searched_states_list;
	if ( nodes_to_search != 0 )
		delete nodes_to_search;
	if ( searched_nodes != 0 )
		delete searched_nodes;
	if ( running_threads != 0 )
		delete running_threads;
};



void mt_search_algorithm::get_buy_commands( const game_state* gs )
{
	//clears current commands queue (not necessary)
	commands.clear();
	cout << "AI BEGIN" << endl;
	time_t start_time = time( 0 );
	
	commands.push_back( "END" );
	
	unsigned int elapsed_sec = ( unsigned int)( abs( ceil ( difftime( time( 0 ), start_time ) ) ) );

	cout << "Elapsed time: " << ai_algorithms::sec_to_string( elapsed_sec ) << " (will not be added to graph)" << endl;
	cout << "AI END" << endl;
};



void mt_search_algorithm::get_commands( const game_state* gs )
{
	commands.clear();
	cout << "AI BEGIN" << endl;
	time_t start_time = time( 0 );

	original_state = gs;

	int ideal_threads = QThread::idealThreadCount();
	if ( ideal_threads == -1 )
		cout << "Optimal threads: unknown (running as single thread)" << endl;
	else
		cout << "Optimal threads count: " << ideal_threads << endl;

	state_levels = new vector< list< ai_states_node_mt* > >( ( unsigned int)( ceil( parameters::get_instance()->ai_parameters[ "SEARCH_MT" ][ "depth" ] ) + 1 ) );
	searched_states_list = new map< unsigned long long int, list< game_state* > >;
	workers = new list< sa_worker* >;

	nodes_to_search = new unsigned int;
	searched_nodes = new unsigned int;
	running_threads = new unsigned int;

	//adding root node
	search_tree = new ai_states_node_mt( 0, new ai_game_state( gs->clone(), "NXT", false ) );
	*nodes_to_search = 1;
	*searched_nodes = 0;
	*running_threads = 0;
	cout << "Nodes searched: " << *searched_nodes << "  -  Remaining: " << *nodes_to_search << "          ";

	//start first thread
	sa_worker* main_thread = new sa_worker( this, search_tree );
	main_thread->start();

	//wait for all threads
	while ( exist_reamaining_nodes() )
		ai_algorithms::suspend( 1000 );
	
	cout << endl;

	//clear threads list
	for ( list< sa_worker* >::iterator it = workers->begin(); it != workers->end(); ++it )
		delete *it;
	workers->clear();

	//compute scores for each level
	for ( unsigned int i = state_levels->size() - 2; i > 0; --i )
	{
		//for each node in level compute his score
		//we predict, that each player will do actions leading to the best score, so we choose that states and try to avoid them with previous player
		for ( list< ai_states_node_mt* >::iterator it = ( *state_levels )[ i ].begin(); it != ( *state_levels )[ i ].end(); ++it )
		{
			ai_states_node_mt* found_node = find_max_score_curr( ( *it )->level_children );
			if ( found_node == 0 )
			{
				( *it )->my_score = -1e50;
				( *it )->current_score = -1e50;
				continue;
			}
			( *it )->my_score = found_node->my_score;
			( *it )->current_score = found_node->prev_score;
		}
	}

	//find best state for me
	ai_states_node_mt* best_node = find_max_score_me( &( *state_levels )[ 1 ] );

	if ( best_node != 0 )
	{
		//get all commands on way from best state
		for ( ai_states_node_mt* i = best_node; i->parent != 0; i = i->parent )
		{
			commands.push_front( i->state->command );
		}
	}
	else
	{
		commands.push_front( "NXT" );
	}

	delete nodes_to_search;
	delete searched_nodes;
	delete running_threads;
	delete search_tree;
	delete state_levels;
	delete searched_states_list;
	delete workers;
	nodes_to_search = 0;
	searched_nodes = 0;
	running_threads = 0;
	search_tree = 0;
	state_levels = 0;
	searched_states_list = 0;
	workers = 0;

	unsigned int elapsed_sec = ( unsigned int)( abs( ceil ( difftime( time( 0 ), start_time ) ) ) );
	time_cons.push_back( elapsed_sec );
	cout << "Elapsed time: " << ai_algorithms::sec_to_string( elapsed_sec ) << endl;
	cout << "AI END" << endl;
};



void mt_search_algorithm::change_nodes_counters( int nts, int sn )
{
	QRWLocker locker( lock_counters, true );
	*nodes_to_search += nts;
	*searched_nodes += sn;
	cout << "\rNodes searched: " << *searched_nodes << "  -  Remaining: " << *nodes_to_search << "          ";
};



void mt_search_algorithm::add_to_state_levels( ai_states_node_mt* state_node )
{
	QRWLocker locker( lock_levels_list, true );
	( *state_levels )[ state_node->depth ].push_back( state_node );
};



void mt_search_algorithm::thread_started()
{
	QRWLocker locker( lock_thread_counter, true );
	++( *running_threads );
};



void mt_search_algorithm::thread_finished()
{
	QRWLocker locker( lock_thread_counter, true );
	--( *running_threads );
};



bool mt_search_algorithm::fork_new_thread()
{
	int ideal_threads = QThread::idealThreadCount();
	if ( ideal_threads == -1 )
		ideal_threads = 1;
	QRWLocker locker( lock_thread_counter, false );
	// if some cores are free -> create more threads
	if ( ( int )( *running_threads ) < ideal_threads )
		return true;
	else
		return false;
};



void mt_search_algorithm::add_worker( sa_worker* worker )
{
	QRWLocker locker( lock_workers_list, true );
	workers->push_back( worker );
};



void mt_search_algorithm::clear_workers()
{
	QRWLocker locker( lock_workers_list, true );
	bool erased = true;
	//clear all finished workers
	while( erased )
	{
		erased = false;
		for ( list< sa_worker* >::iterator it = workers->begin(); it != workers->end(); ++it )
		{
			if ( ( *it )->isFinished() )
			{
				delete *it;
				workers->erase( it );
				erased = true;
				break;
			}
		}
	}
};



bool mt_search_algorithm::exist_reamaining_nodes()
{
	clear_workers();
	QRWLocker locker( lock_workers_list, false );
	return !workers->empty();
};



void mt_search_algorithm::add_to_list( game_state* state )
{
	QRWLocker locker( lock_searched_states_list, true );
	( *searched_states_list )[ state->get_hash() ].push_back( state );
};



bool mt_search_algorithm::is_in_list( game_state* state )
{
	QRWLocker locker( lock_searched_states_list, false );
	map< unsigned long long int, list< game_state* > >::iterator found_pair = searched_states_list->find( state->get_hash() );
	if ( found_pair == searched_states_list->end() )
		return false;
	//state with same hash exists
	list< game_state* > found_states = found_pair->second;
	//check if the states are really the same
	for ( list< game_state* >::iterator it = found_states.begin(); it != found_states.end(); ++it )
		if ( ( *it )->equals( state ) )
			return true;
	return false;
};



void sa_worker::search_state( ai_states_node_mt* state_node )
{
	main_mt_sa->add_to_list( state_node->state->state );
	main_mt_sa->change_nodes_counters( -1, 1 );
	if ( state_node->state->command == "NXT" )
	{
		++state_node->depth;
		state_node->state->state->get_map_structures_from_state( main_mt_sa->original_state );
		state_node->state->state->update_score_structures();
		main_mt_sa->add_to_state_levels( state_node );

		//connect levels
		ai_states_node_mt* connect_node = state_node->parent;
		while ( ( connect_node != 0 ) && ( connect_node->state->command != "NXT" ) )
		{
			connect_node = connect_node->parent;
		}

		state_node->level_parent = connect_node;
		if ( connect_node != 0 )
		{
			connect_node->add_level_children( state_node );
			state_node->prev_score = state_node->state->state->another_plrs_score( state_node->level_parent->state->state->current_player_id );
		}

		if ( state_node->depth >= parameters::get_instance()->ai_parameters[ "SEARCH_MT" ][ "depth" ] )
		{
			//save my score to leafs
			state_node->my_score = state_node->state->state->another_plrs_score( main_mt_sa->get_owner()->get_id() );
			return;
		}
	}
	state_node->state->state->clear_all_structures();
	//generate all possible children
	ai_states_node_mt* generated_node;
	ai_game_state* generated_state;
	game_state* test_gs;
	player* test_pl;
	unit* test_u;
	unsigned int max_range_move;
	//for search only of possible square
	unsigned int search_top;
	unsigned int search_left;
	unsigned int search_bottom;
	unsigned int search_right;
	for ( unsigned int u = 0; u < state_node->state->state->plrs[ state_node->state->state->current_player_id ]->units.size(); ++u )
	{
		test_pl = state_node->state->state->plrs[ state_node->state->state->current_player_id ];
		test_u = test_pl->units[ u ];
		max_range_move = test_u->get_range() > ( test_pl->get_time() / test_u->get_cost_move() ) ? test_u->get_range() : ( test_pl->get_time() / test_u->get_cost_move() / 10 );
		//compute search ranges (square where to search for possibilities)
		search_top = ( ( ( int )test_u->get_y() - ( int )max_range_move ) > 0 ) ? ( test_u->get_y() - max_range_move ) : 0;
		search_left = ( ( ( int )test_u->get_x() - ( int )max_range_move ) > 0 ) ? ( test_u->get_x() - max_range_move ) : 0;
		search_bottom = ( ( test_u->get_y() + max_range_move ) < mapa::get_instance()->get_size_y() ) ? ( test_u->get_y() + max_range_move ) : ( mapa::get_instance()->get_size_y() - 1 );
		search_right = ( ( test_u->get_x() + max_range_move ) < mapa::get_instance()->get_size_x() ) ? ( test_u->get_x() + max_range_move ) : ( mapa::get_instance()->get_size_x() - 1 );
		for ( unsigned int x = search_left; x <= search_right; ++x )
			for ( unsigned int y = search_top; y <= search_bottom; ++y )
			{
				test_gs = state_node->state->state->clone();
				if ( ai_support_computations::ai_fire( test_gs->plrs[ test_gs->current_player_id ]->units[ u ], x, y, test_gs ) )
				{
					//generate state by attacking
					generated_state = new ai_game_state( state_node->state->state, game::create_command( "ATT", u, x, y ) );
					if ( main_mt_sa->is_in_list( generated_state->state ) )
					{
						delete generated_state;
					}
					else
					{
						generated_node = new ai_states_node_mt( state_node, generated_state );
					}
				}
				delete test_gs;
				test_gs = state_node->state->state->clone();
				if ( ai_support_computations::ai_move( test_gs->plrs[ test_gs->current_player_id ]->units[ u ], x, y, test_gs ) )
				{
					//generate state by moving
					generated_state = new ai_game_state( state_node->state->state, game::create_command( "MOV", u, x, y ) );
					if ( main_mt_sa->is_in_list( generated_state->state ) )
					{
						delete generated_state;
					}
					else
					{
						generated_node = new ai_states_node_mt( state_node, generated_state );
					}
				}
				delete test_gs;
			}
	}

	//adding end of the turn as the last possibility to do
	generated_state = new ai_game_state( state_node->state->state, "NXT" );
	if ( main_mt_sa->is_in_list( generated_state->state ) )
	{
		delete generated_state;
	}
	else
	{
		generated_node = new ai_states_node_mt( state_node, generated_state );
	}

	main_mt_sa->change_nodes_counters( state_node->children->size(), 0 );
	//recursive call to all new children
	sa_worker* worker;
	for ( list< ai_states_node_mt* >::iterator it = state_node->children->begin(); it != state_node->children->end(); ++it )
	{
		if ( main_mt_sa->fork_new_thread() )
		{
			//free core
			worker = new sa_worker( main_mt_sa, *it );
			worker->start();
		}
		else
		{
			//no free core
			search_state( *it );
		}
	}
};



ai_states_node_mt* mt_search_algorithm::find_max_score_me( list< ai_states_node_mt* >* node_list )
{
	if ( node_list->empty() )
		return 0;
	ai_states_node_mt* found_node = *( node_list->begin() );
	for ( list< ai_states_node_mt* >::iterator it = node_list->begin(); it != node_list->end(); ++it )
		if ( ( *it )->my_score > found_node->my_score )
			found_node = ( *it );
	return found_node;
};



ai_states_node_mt* mt_search_algorithm::find_max_score_curr( list< ai_states_node_mt* >* node_list )
{
	if ( node_list->empty() )
	{
		return 0;
	}
	ai_states_node_mt* found_node = *( node_list->begin() );
	for ( list< ai_states_node_mt* >::iterator it = node_list->begin(); it != node_list->end(); ++it )
		if ( ( *it )->current_score > found_node->current_score )
			found_node = ( *it );
	return found_node;
};



ai_states_node_mt* mt_search_algorithm::find_max_score_prev( list< ai_states_node_mt* >* node_list )
{
	if ( node_list->empty() )
		return 0;
	ai_states_node_mt* found_node = *( node_list->begin() );
	for ( list< ai_states_node_mt* >::iterator it = node_list->begin(); it != node_list->end(); ++it )
		if ( ( *it )->prev_score > found_node->prev_score )
			found_node = ( *it );
	return found_node;
};



ai_states_node_mt::ai_states_node_mt( ai_states_node_mt* p, ai_game_state* s )
{
	lock_level_children = new QReadWriteLock();
	children = new list< ai_states_node_mt* >;
	level_children = new list< ai_states_node_mt* >;
	state = s;
	parent = p;
	level_parent = 0;
	my_score = 0;
	prev_score = 0;
	current_score = s->state->score;
	if ( p != 0 )
	{
		p->children->push_back( this );
		depth = p->depth;
	}
	else
	//root node
	{
		prev_score = 0;
		//first pass will increase it to 0
		depth = -1;
	}
};



ai_states_node_mt::~ai_states_node_mt()
{
	if ( !children->empty() )
		for ( list< ai_states_node_mt* >::iterator it = children->begin(); it != children->end(); ++it )
		{
			delete *it;
		}
	delete children;
	delete level_children;
	delete lock_level_children;
	delete state;
};



void ai_states_node_mt::add_level_children( ai_states_node_mt* lev_child )
{
	QRWLocker locker( lock_level_children, true );
	level_children->push_back( lev_child );
};